﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0156_GetRow : IAlgorithm
    {
        // 杨辉三角 II

        // 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
        // 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

        // 提示:
        //  0 <= rowIndex <= 33

        // 进阶：
        //  你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
        
        public void Test()
        {
            var res = GetRow(1);
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public IList<int> GetRow(int rowIndex)
        {
            List<int> row = new List<int>();
            row.Add(1);
            for (int i = 1; i <= rowIndex; ++i)
                row.Add((int)((long)row[i - 1] * (rowIndex - i + 1) / i));
            return row;
        }
    }
}
